// https://leetcode-cn.com/problems/top-k-frequent-elements/
// 347. Top K Frequent Elements
// Given an integer array nums and an integer k, return the k most frequent
// elements. You may return the answer in any order.
function topKFrequent(nums: number[], k: number): number[] {
    const freq: Map<number, number> = new Map();
    for (let n of nums) {
        freq.set(n, (freq.get(n) || 0) + 1);
    }

    interface Item {
        num: number;
        val: number;
    }

    const result: Item[] = [];
    for (let [num, val] of freq) {
        if (result.length < k) {
            result.push({ num, val });
            swim(result, result.length - 1);
        } else {
            if (val > result[0].val) {
                result[0] = { num, val };
                sink(result);
            }
        }
    }

    function compare(arr: Item[], a: number, b: number): boolean {
        return arr[a].val < arr[b].val;
    }

    function pid(n: number): number {
        return ((n - 1) / 2) >> 0;
    }

    function swap<T>(arr: Array<T>, a: number, b: number): void {
        [arr[b], arr[a]] = [arr[a], arr[b]];
    }

    function swim(arr: Item[], i: number) {
        while (i > 0) {
            const p = pid(i);
            if (compare(arr, i, p)) {
                swap(arr, i, p);
            }
            i = p;
        }
    }

    function sink(arr: Item[]): void {
        let i = 0;
        while (2 * i + 1 < arr.length) {
            let j = 2 * i + 1;
            if (j + 1 < arr.length && compare(arr, j + 1, j)) {
                j += 1;
            }
            if (compare(arr, i, j)) {
                break;
            }
            swap(arr, i, j);
            i = j;
        }
    }

    return result.map((item) => item.num);
}

// const result = topKFrequent([3, 0, 1, 0], 1);
// console.log(result);
